package leetcode;

/**
 * description:
 * author:zt
 * date:2022-05-28
 */

import java.util.LinkedList;

/**
 * 有效括号字符串为空 ""、"(" + A + ")"或A + B ，其中A 和B都是有效的括号字符串，+代表字符串的连接。
 *
 * 例如，""，"()"，"(())()"和"(()(()))"都是有效的括号字符串。
 * 如果有效字符串 s 非空，且不存在将其拆分为 s = A + B的方法，我们称其为原语（primitive），其中A 和B都是非空有效括号字符串。
 *
 * 给出一个非空有效字符串 s，考虑将其进行原语化分解，使得：s = P_1 + P_2 + ... + P_k，其中P_i是有效括号字符串原语。
 *
 * 对 s 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 s 。
 */
public class leetcode1021 {
    public String removeOuterParentheses(String s) {
        StringBuilder sb = new StringBuilder();
        LinkedList<Character> stack = new LinkedList<>();
        int left = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') stack.push('(');
            else stack.pop();

            if (stack.size() == 0) {
                if ((i-left) > 1) sb.append(s, left + 1, i);
                left = i + 1;
            }
        }
        return sb.toString();
    }
}
